#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "envel.h"
#include "Lab4.h"
#include "constantes.h"

void LiberaPilhaouFila(ApPilha Estrutura)
{
	/* libera estrutura do ultimo para o primeiro no', recursivamente*/
	if (Estrutura->prox == NULL) free(Estrutura);
	else
	{
		LiberaPilhaouFila(Estrutura->prox);
		free(Estrutura);
	}
}

void carregaConfiguracoes (char **mensagens)
{
	FILE *configuracoes;
	char string[100], chr;
	int i=0, j=0;

	configuracoes = fopen("config.txt", "r");

	while (!feof(configuracoes)) //enquanto nao fim de arquivo
	{
		chr = getc(configuracoes);
	    while (chr != EOF && chr != '\n')//condicao de fim de mensagem
	    {
	    	string[i] = chr;
	        i++;
	        chr = getc(configuracoes);
	    }
	    string[i] = '\0';//null-character colocado no fim desta string
	    mensagens[j] = (char *)Malloc(strlen(string)+4);//aloca espaco para mensagem
	    strcpy(mensagens[j], string);//mensagem adicionada ao vetor de string
	    j++;
	    i=0;
	}
	fclose(configuracoes);

}

int verificaParametros(char *mensagens[], int ordem, char *dados[])
{
	FILE *f;
	f = fopen(dados, "r");
	/*verifica existencia do arquivo de dados*/
	if(!arqExistente(f))
	{
	    printf("%s\n", mensagens[1]); //arquivo inexistente
	    return false;
	}
	fclose(f);

	/*verifica se a ordem passada respeita o intervalo descrito pelo enunciado*/
	if (ordem < 3 || ordem > 10)
	{
		printf("%s\n", mensagens[10]);
		return false;
	}
	return true;

}

void extraiChaves(char *dados[])
{
        FILE *entrada, *arqChaves;
        int i, bytes = 0, bytesRegistro;
        char aux;
        entrada = fopen(dados, "r"); //abre arquivo de dados
        arqChaves = fopen(ARQUIVOCHAVES, "w"); //abre arquivo de chaves primarias

        while (1)
        {
			  bytesRegistro = 0;
              i = 6;

              while (i > 0)
              /* neste loop copiamos a chaves primaria, no caso, o RA,
              de tamanho fixo = 6, para o arq de chaves*/
              {
                    aux = getc(entrada);
                    bytesRegistro++;
                    bytes++;
                    fprintf(arqChaves, "%c", aux);
                    i--;
              }
              fprintf(arqChaves, "%c", CARACTERSEPARADOR);
              /*Separamos chave de seu endereco com CARACTERSEPARADOR*/
              while(aux != FIMREGISTRO)
              /*neste loop contamos quantos bytes o registro tem*/
              {
                    aux = getc(entrada);
                    bytesRegistro++;
                    bytes++;
              }
              fprintf(arqChaves, "%08d\n", bytes-bytesRegistro);
              /*imprimimos no arq de chaves o endereco que comeca este registro*/
              aux = getc(entrada);
              bytesRegistro++;
              bytes++;

              aux = getc(entrada);

              /*condicao para sair do loop: fim do arq de dados*/
              if (feof(entrada)) break;
              else ungetc(aux, entrada);
        }
        fclose (entrada);
        fclose (arqChaves);
}

void cardapio(char *mensagens[], int ordem, char dados[0], char indice[0], char desprezadas[0], char descricao[0]) //Funcao cardapio
{
	int opcao = 0;

	while(opcao != 4){

		printf("%s\n%s\n%s\n%s\n%s\n\n", mensagens[2], mensagens[2], mensagens[3], mensagens[2], mensagens[2]);
		printf("%s\n%s\n%s\n%s\n%s", mensagens[4], mensagens[5], mensagens[6], mensagens[7], mensagens[8]);

		//aqui comeca os switches para as opcoes
		scanf("%d", &opcao);

		switch (opcao){

		case 1:
				constroiArvore(mensagens, ordem, dados, indice, desprezadas);
				printf("\n\n%s\n\n", mensagens[11]);
				break;
		case 2:
				if (geraArquivoEstrutura(indice, ordem, descricao)) printf("\n\n%s\n\n", mensagens[12]);
				else printf("\n\n%s\n\n", mensagens[13]);
				break;
		case 3:
				if (!pesquisaBaseDados(mensagens, dados, indice, ordem))
					printf("\n\n%s\n\n", mensagens[14]);
				break;
		case 4:
				break;
		default:
				printf("\n%s\n", mensagens[9]);
				break;
		}
	}
}

void desprezaRegistro(FILE *Dados, int RRN_atual, FILE *Desprezadas)
{
	char aux;
	fseek(Dados, RRN_atual, SEEK_SET); //achamos o registro no arquivo de dados
	aux = getc(Dados);
	while(aux != '\n')
	{
		fputc(aux, Desprezadas);	//copia o registro a ser desprezado para o arquivo
		aux = getc(Dados);
	}
	fputc(aux, Desprezadas);
}

int calculaTamanhoPorPagina(int ordem)
{
	return (((ordem-1)*6) + (ordem - 2) + 1) + (((ordem-1)*8) + (ordem - 2) + 1) + (((ordem)*6) + (ordem - 1) + 2) + TAM_HEADER_PAGINA;
}

void constroiArvore(char *mensagens[], int ordem, char *dados[], char *indice[], char *desprezadas[])
{
	FILE *Dados, *ArvB, *Desprezadas, *arqChaves;
	int num_paginas = 1, *vetor_chaves, *vetor_RRN, *vetor_filhos, chave_atual, RRN_atual, eh_folha, n_chaves, pagina_atual, i, j, tam_bytes_pagina, pagina_raiz = 1, eh_repetido = 0, maior = 0;
	char aux[9], aux2;
	ApPilha Pilha = NULL, auxPilha = NULL;

	extraiChaves(dados);	//extrai as chaves primarias e RRNs dos registros

	/* abre arquivos a serem utilizados pela funcao */
	arqChaves = fopen(ARQUIVOCHAVES, "r");
	ArvB = fopen(indice, "w+");
	Dados = fopen(dados, "r");
	Desprezadas = fopen(desprezadas, "w");

	/* imprime o header da Arvore B, que informa quantos nos e qual pagina eh a raiz */
	fprintf(ArvB, "PAGS: %06d\nRAIZ: %06d\n\n", num_paginas, pagina_raiz);

	/* cria primeira pagina, correspondente a raiz */
	criaPagina(ArvB, num_paginas, ordem, 1, 0);

	/* calcula quantos bytes cada no da arvore ocupa, dependendo da ordem */
	tam_bytes_pagina = calculaTamanhoPorPagina(ordem);

	while (1) //montagem da Arvore até as chaves extraidas se esgotarem
	{
		/* obtemos chave a ser inserida na Arvore B */
		for(i = 0; i < 6; i++)
		{
			aux[i] = getc(arqChaves);
		}
		aux[i] = '\0';
		chave_atual = converteInt2(aux);

		/* obtemos RRN da chave a ser inserida na Arvore B */
		aux2 = getc(arqChaves);
		for(i = 0; i < 8; i++)
		{
			aux[i] = getc(arqChaves);
		}
		aux[i] = '\0';
		RRN_atual = converteInt2(aux);

		fseek(ArvB, TAM_HEADER_ARVORE + ((pagina_raiz-1)*tam_bytes_pagina), SEEK_SET);

		/* Pilha que representara o percurso feito pela Arvore */
		Pilha = Malloc(sizeof(pilha));
		Pilha->pagina = pagina_raiz;
		Pilha->pagina_eh_raiz = true;
		Pilha->prox = NULL;
		auxPilha = Pilha;

		/* obtencao do numero da pagina atual, numero de chaves nela contida
		 * e se ela eh uma folha ou nao, atraves do seu header */
		aux2 = getc(ArvB);
		while(aux2 != ' ') aux2 = getc(ArvB);
		fscanf(ArvB, "%d", &pagina_atual);
		aux2 = getc(ArvB);
		while(aux2 != ' ') aux2 = getc(ArvB);
		fscanf(ArvB, "%d", &n_chaves);
		aux2 = getc(ArvB);
		while(aux2 != ' ') aux2 = getc(ArvB);
		fscanf(ArvB, "%d", &eh_folha);

		/* desce pela Arvore enquanto nao chega numa folha, e nao encontrou
		 * a chave jah presente na Arvore B */
		while (!eh_folha && !eh_repetido)
		{
			/* Aloca vetores */
			vetor_chaves = (int*)Malloc((ordem - 1)*sizeof(int));
			vetor_filhos = (int*)Malloc((ordem)*sizeof(int));
			while(aux2 != '*') aux2 = getc(ArvB);
			aux2 = getc(ArvB);

			/* Carrega o vetor de chaves ordenadas e seus respectivos filhos
			 * do disco para a memória, para melhor gerenciamento */
			for (i = 0; i < ordem - 1; i++)
			{
				for (j = 0; j < 6; j++) aux[j] = getc(ArvB);
				aux[j] = '\0';
				vetor_chaves[i] = converteInt2(aux);
				aux2 = getc(ArvB);
			}
			for (i = 0; i < (ordem-1)*8 + ordem-2 + 1; i++) aux2 = getc(ArvB); //pula vetor de RRNs
			for (i = 0; i < ordem; i++)
			{
				for (j = 0; j < 6; j++) aux[j] = getc(ArvB);
				aux[j] = '\0';
				vetor_filhos[i] = converteInt2(aux);
				aux2 = getc(ArvB);
			}
			i = 0;

			/* encontra posicao no vetor de chaves a ser inserido a chave atual */
			while ((vetor_chaves[i] < chave_atual) && (vetor_chaves[i] != -1))
			{
				if (i == ordem-2)
				{
					maior = true; //chave a ser inserida eh maior que as outras no vetor
					break;
				}
				i++;
			}
			if (chave_atual == vetor_chaves[i]) eh_repetido = true; //levanta flag de repetido
			if (!maior) pagina_atual = vetor_filhos[i];
			else pagina_atual = vetor_filhos[i+1];
			maior = false;

			free(vetor_chaves);
			free(vetor_filhos);

			/* desce um nivel na arvore */
			fseek(ArvB, TAM_HEADER_ARVORE + ((pagina_atual-1)*tam_bytes_pagina), SEEK_SET);

			/* empilha esta pagina na pilha de percurso */
			auxPilha->prox = Malloc(sizeof(pilha));
			auxPilha = auxPilha->prox;
			auxPilha->pagina = pagina_atual;
			auxPilha->pagina_eh_raiz = false;
			auxPilha->prox = NULL;

			/* obtencao do numero da pagina atual, numero de chaves nela contida
			 * e se ela eh uma folha ou nao, atraves do seu header */
			aux2 = getc(ArvB);
			while(aux2 != ' ') aux2 = getc(ArvB);
			fscanf(ArvB, "%d", &pagina_atual);
			aux2 = getc(ArvB);
			while(aux2 != ' ') aux2 = getc(ArvB);
			fscanf(ArvB, "%d", &n_chaves);
			aux2 = getc(ArvB);
			while(aux2 != ' ') aux2 = getc(ArvB);
			fscanf(ArvB, "%d", &eh_folha);

		}
		/* despreza registro jah presente na Arvore B */
		if (eh_repetido) desprezaRegistro(Dados, RRN_atual, Desprezadas);
		else
		{
			/* Aloca vetores */
			vetor_chaves = (int*)Malloc((ordem)*sizeof(int));
			vetor_RRN = (int*)Malloc((ordem)*sizeof(int));
			vetor_filhos = (int*)Malloc((ordem+1)*sizeof(int));

			while(aux2 != '*') aux2 = getc(ArvB);
			aux2 = getc(ArvB);

			/* Carrega o vetor de chaves ordenadas e seus respectivos RRNs e filhos
			 * do disco para a memória, para melhor gerenciamento, atribuindo o valor
			 * -1 para posicoes vazias do vetor (isso jah eh feito por converteInt2) */
			for (i = 0; i < ordem - 1; i++)
			{
				for (j = 0; j < 6; j++) aux[j] = getc(ArvB);
				aux[j] = '\0';
				vetor_chaves[i] = converteInt2(aux);
				aux2 = getc(ArvB);
			}
			vetor_chaves[i] = -1;
			for (i = 0; i < ordem - 1; i++)
			{
				for (j = 0; j < 8; j++) aux[j] = getc(ArvB);
				aux[j] = '\0';
				vetor_RRN[i] = converteInt2(aux);
				aux2 = getc(ArvB);
			}
			vetor_RRN[i] = -1;
			for (i = 0; i < ordem; i++)
			{
				for (j = 0; j < 6; j++) aux[j] = getc(ArvB);
				aux[j] = '\0';
				vetor_filhos[i] = converteInt2(aux);
				aux2 = getc(ArvB);
			}
			vetor_filhos[i] = -1;

			/* encontra posicao no vetor de chaves a ser inserido a chave atual */
			i = 0;
			while (vetor_chaves[i] < chave_atual && vetor_chaves[i] != -1) i++;

			/* se nesta folha a chave atual jah estava presente */
			if (vetor_chaves[i] == chave_atual) desprezaRegistro(Dados, RRN_atual, Desprezadas);
			else
			{
				n_chaves++;

				/* desloca os elementos dos vetores para a direita, para futura
				 * acomodacao da chave atual */
				for (j = ordem-1; j > i; j--)
				{
					vetor_chaves[j] = vetor_chaves[j-1];
					vetor_RRN[j] = vetor_RRN[j-1];
					vetor_filhos[j+1] = vetor_filhos[j];
				}

				/* a chave atual e seu RRN eh finalmente inserido na Arvore B */
				vetor_chaves[i] = chave_atual;
				vetor_RRN[i] = RRN_atual;

				/* caso esta folha tenha tido overflow, ajusta a Arvore B */
				if (n_chaves > ordem-1) ajustaOverflow(ArvB, &num_paginas, &pagina_raiz, ordem, vetor_chaves, vetor_RRN, vetor_filhos, Pilha, tam_bytes_pagina);
				else
				{
					fseek(ArvB, TAM_HEADER_ARVORE + ((pagina_atual-1)*tam_bytes_pagina) + 23, SEEK_SET);

					/* Atualiza o header desta folha, incrementando seu numero de chaves,
					 * e inserindo o novo elemento no disco */
					fprintf(ArvB, "%d", n_chaves);
					for (i = 0; i < 14; i++) aux2 = getc(ArvB);

					/* Transferencia da informacao dos vetores da memoria para o disco*/
					fprintf(ArvB, "%06d", vetor_chaves[0]);
					for (i = 1; i < ordem - 1; i++)
					{
						if(vetor_chaves[i] != -1) fprintf(ArvB, "%c%06d", CARACTERSEPARADOR, vetor_chaves[i]);
						else fprintf(ArvB, "%c      ", CARACTERSEPARADOR);
					}
					aux2 = getc(ArvB);
					fprintf(ArvB, "%08d", vetor_RRN[0]);
					for (i = 1; i < ordem - 1; i++)
					{
						if(vetor_chaves[i] != -1) fprintf(ArvB, "%c%08d", CARACTERSEPARADOR, vetor_RRN[i]);
						else fprintf(ArvB, "%c        ", CARACTERSEPARADOR);
					}
				}
			/* Libera memoria usada para os vetores*/
			free(vetor_chaves);
			free(vetor_RRN);
			free(vetor_filhos);
			}
		}
		eh_repetido = false;

		/* Libera memoria usada para a Pilha de percurso na Arvore */
		LiberaPilhaouFila(Pilha);

		aux2 = getc(arqChaves); aux2 = getc(arqChaves);
		if(feof(arqChaves)) break; //caso as chaves acabaram
		else ungetc(aux2, arqChaves);
	}

	/* atualiza header da Arvore B */
	fseek(ArvB, 6, SEEK_SET);
	fprintf(ArvB, "%06d\nRAIZ: %06d", num_paginas, pagina_raiz);

	/* Fecha arquivos utilizados pela funcao */
	fclose(arqChaves);
	fclose(ArvB);
	fclose(Dados);
	fclose(Desprezadas);
}

void criaPagina(FILE *ArvB, int num_paginas, int ordem, int folha, int n_keys)
{
	int i = 0;

	/* vai ao final do arquivo de indice para incluir um novo nó */
	fseek(ArvB, 0, SEEK_END);

	/* escreve header da pagina */
	fprintf(ArvB, "PAGINA: %06d\n", num_paginas);
	fprintf(ArvB, "N_KEYS: %d\n", n_keys);
	if (folha) fprintf(ArvB, "EFOLHA: %d\n\n", 1);
	else fprintf(ArvB, "EFOLHA: %d\n\n", 0);

	/* aloca espaco para os 3 vetores, de chaves, RRNs e apontadores para filhos */
	fprintf(ArvB, "*\n      ");
	for (i = 1; i < ordem - 1; i++)
		fprintf(ArvB, "%c      ", CARACTERSEPARADOR);
	fprintf(ArvB, "\n        ");
	for (i = 1; i < ordem - 1; i++)
		fprintf(ArvB, "%c        ", CARACTERSEPARADOR);
	fprintf(ArvB, "\n      ");
	for (i = 1; i < ordem; i++)
		fprintf(ArvB, "%c      ", CARACTERSEPARADOR);
	fprintf(ArvB, "\n\n");
}

void ajustaOverflow(FILE *ArvB, int *num_paginas, int *pagina_raiz, int ordem, int *vetor_chaves, int *vetor_RRN, int *vetor_filhos, ApPilha Pilha, int tam_bytes_pagina)
{
		int i, j, eh_folha = false, n_keys;
		char aux, aux2[9];
		promocao Promocao;
		ApPilha auxPilha = Pilha, auxPilha2;

		/* struct Promocao guarda informacoes da chave a ser promovida */
		Promocao.chave = vetor_chaves[(ordem)/2];
		Promocao.RRN = vetor_RRN[(ordem)/2];
		Promocao.filho_dir = vetor_filhos[(ordem/2)+1];
		Promocao.filho_esq = vetor_filhos[(ordem)/2];

		while (auxPilha->prox != NULL) auxPilha = auxPilha->prox;
		//vai para o topo da pilha, ou seja, a folha na qual houve overflow

		do
		{
			/* seek para a pagina que houve overflow, que sera quebrada */
			fseek(ArvB, TAM_HEADER_ARVORE + (((auxPilha->pagina)-1)*tam_bytes_pagina) + 23, SEEK_SET);

			/* atualiza o numero de chaves que ficara no nó, apos a quebra */
			fprintf(ArvB, "%d\nEFOLHA: ", ordem/2);
			aux = getc(ArvB);
			if (aux == '1') eh_folha = true;
			else eh_folha = false;
			aux = getc(ArvB); aux = getc(ArvB); aux = getc(ArvB); aux = getc(ArvB);

			/* escreve na pagina a ser quebrada a metade da esqueda dos seus vetores */
			fprintf(ArvB, "%06d", vetor_chaves[0]);
			for (i = 1; i < ordem - 1; i++)
			{
				if(i < (ordem/2)) fprintf(ArvB, "%c%06d", CARACTERSEPARADOR, vetor_chaves[i]);
				else fprintf(ArvB, "%c      ", CARACTERSEPARADOR);
			}
			fprintf(ArvB, "\n");
			fprintf(ArvB, "%08d", vetor_RRN[0]);
			for (i = 1; i < ordem - 1; i++)
			{
				if(i < (ordem/2)) fprintf(ArvB, "%c%08d", CARACTERSEPARADOR, vetor_RRN[i]);
				else fprintf(ArvB, "%c        ", CARACTERSEPARADOR);
			}
			fprintf(ArvB, "\n");
			if (vetor_filhos[0] == -1) fprintf(ArvB, "      ");
			else fprintf(ArvB, "%06d", vetor_filhos[0]);
			for (i = 1; i < ordem; i++)
			{
				if(i <= (ordem/2))
				{
					if (vetor_filhos[i] == -1) fprintf(ArvB, "%c      ", CARACTERSEPARADOR);
					else fprintf(ArvB, "%c%06d", CARACTERSEPARADOR, vetor_filhos[i]);
				}
				else fprintf(ArvB, "%c      ", CARACTERSEPARADOR);
			}
			fprintf(ArvB, "\n");
			/* fim da atualizacao da pagina que foi quebrada */

			/* cria pagina que recebera a metade da direita dos vetores da pagina que
			 * foi quebrada e em seguida da um seek para ela */
			*num_paginas = *num_paginas + 1;
			criaPagina(ArvB, *num_paginas, ordem, eh_folha, (ordem-1)/2);
			fseek(ArvB, TAM_HEADER_ARVORE + ((*num_paginas-1)*tam_bytes_pagina) + TAM_HEADER_PAGINA, SEEK_SET);

			/* escreve na pagina nova a metade da direita dos vetores */
			j = (ordem/2) + 1;
			fprintf(ArvB, "%06d", vetor_chaves[j]);
			for (i = 1; i < ordem - 1; i++)
			{
				j++;
				if(j < ordem) fprintf(ArvB, "%c%06d", CARACTERSEPARADOR, vetor_chaves[j]);
				else fprintf(ArvB, "%c      ", CARACTERSEPARADOR);
			}
			fprintf(ArvB, "\n");
			j = (ordem/2) + 1;
			fprintf(ArvB, "%08d", vetor_RRN[j]);
			for (i = 1; i < ordem - 1; i++)
			{
				j++;
				if(j < ordem) fprintf(ArvB, "%c%08d", CARACTERSEPARADOR, vetor_RRN[j]);
				else fprintf(ArvB, "%c        ", CARACTERSEPARADOR);
			}
			fprintf(ArvB, "\n");
			j = (ordem/2) + 1;
			if (vetor_filhos[j] == -1) fprintf(ArvB, "      ");
			else fprintf(ArvB, "%06d", vetor_filhos[j]);
			for (i = 1; i < ordem; i++)
			{
				j++;
				if(j <= ordem)
				{
					if (vetor_filhos[j] == -1 || vetor_filhos[j] == 0) fprintf(ArvB, "%c      ", CARACTERSEPARADOR);
					else fprintf(ArvB, "%c%06d", CARACTERSEPARADOR, vetor_filhos[j]);
				}
				else fprintf(ArvB, "%c      ", CARACTERSEPARADOR);
			}
			fprintf(ArvB, "\n");
			/* fim da escrita da nova pagina criada */

			/* atualiza a struct, guardando qual chave do overflow sera promovida */
			Promocao.chave = vetor_chaves[(ordem)/2];
			Promocao.RRN = vetor_RRN[(ordem)/2];
			Promocao.filho_esq = auxPilha->pagina; //filho esquerdo eh a pagina que foi quebrada
			Promocao.filho_dir = *num_paginas; //filho direito eh a pagina que foi criada

			/* se a quebra anterior foi feita na raiz, uma nova raiz devera
			 * ser criada */
			if (auxPilha->pagina_eh_raiz)
			{
				*num_paginas = *num_paginas + 1;

				/* cria nova raiz */
				criaPagina(ArvB, *num_paginas, ordem, 0, 1);
				*pagina_raiz = *num_paginas;
				fseek(ArvB, TAM_HEADER_ARVORE + ((*pagina_raiz-1)*tam_bytes_pagina) + TAM_HEADER_PAGINA, SEEK_SET);
				fprintf(ArvB, "%06d", Promocao.chave);
				for (i = 0; i < (ordem-1)*6 + ordem-2 + 1 - 6; i++) aux = getc(ArvB);
				fprintf(ArvB, "%08d", Promocao.RRN);
				for (i = 0; i < (ordem-1)*8 + ordem-2 + 1 - 8; i++) aux = getc(ArvB);
				fprintf(ArvB, "%06d%c%06d", auxPilha->pagina, CARACTERSEPARADOR, *num_paginas - 1);
				Promocao.chave = -1;
			}
			else
			{
				/* volta pelo percurso na pilha, para insercao da chave promovida
				 * no noh pai */
				auxPilha2 = Pilha;
				while (auxPilha2->prox != auxPilha) auxPilha2 = auxPilha2->prox;
				free(auxPilha);
				auxPilha2->prox = NULL; auxPilha = auxPilha2;

				/* seek para a pagina pai */
				fseek(ArvB, TAM_HEADER_ARVORE + (((auxPilha->pagina)-1)*tam_bytes_pagina) + 23, SEEK_SET);
				fscanf(ArvB, "%d", &n_keys);
				while (aux != '*') aux = getc(ArvB);
				aux = getc(ArvB);

				/* carrega os vetores de chaves, RRNs e apontadores para filhos da pagina
				 * pai do disco para a memoria */
				for (i = 0; i < ordem - 1; i++)
				{
					for (j = 0; j < 6; j++) aux2[j] = getc(ArvB);
					aux2[j] = '\0';
					vetor_chaves[i] = converteInt2(aux2);
					aux = getc(ArvB);
				}
				for (i = 0; i < ordem - 1; i++)
				{
					for (j = 0; j < 8; j++) aux2[j] = getc(ArvB);
					aux2[j] = '\0';
					vetor_RRN[i] = converteInt2(aux2);
					aux = getc(ArvB);
				}
				for (i = 0; i < ordem; i++)
				{
					for (j = 0; j < 6; j++) aux2[j] = getc(ArvB);
					aux2[j] = '\0';
					vetor_filhos[i] = converteInt2(aux2);
					aux = getc(ArvB);
				}

				/* encontra no vetor de chaves do pai a posicao ser inserido a chave promovida */
				i = 0;
				while (vetor_chaves[i] < Promocao.chave && vetor_chaves[i] != -1) i++;
				n_keys++;

				/* desloca para a direita os elementos dos vetores para acomodacao da chave
				 * promovida */
				for (j = ordem-1; j > i; j--)
				{
					vetor_chaves[j] = vetor_chaves[j-1];
					vetor_RRN[j] = vetor_RRN[j-1];
					vetor_filhos[j+1] = vetor_filhos[j];
				}

				/* chave promovida eh finalmente inserida no noh pai */
				vetor_chaves[i] = Promocao.chave;
				vetor_RRN[i] = Promocao.RRN;
				vetor_filhos[i] = Promocao.filho_esq;
				vetor_filhos[i+1] = Promocao.filho_dir;

				/* se houve overflow do pai */
				if (n_keys > ordem-1)
				{
					/* atualiza a struct Promocao, para repetir o ciclo da funcao */
					Promocao.chave = vetor_chaves[(ordem)/2];
					Promocao.RRN = vetor_RRN[(ordem)/2];
					Promocao.filho_dir = vetor_filhos[(ordem/2)+1];
					Promocao.filho_esq = vetor_filhos[(ordem)/2];
				}
				else //noh pai recebeu chave promovida sem ocorrer overflow
				{
					/* seek para o noh pai */
					fseek(ArvB, TAM_HEADER_ARVORE + (((auxPilha->pagina)-1)*tam_bytes_pagina) + 23, SEEK_SET);

					/* atualiza header da pagina, aumentando o numero de chaves nela */
					fprintf(ArvB, "%d", n_keys);
					for(i = 0; i < 14; i++) aux = getc(ArvB);

					/* passagem da memoria para o disco do noh pai, jah atualizado */
					fprintf(ArvB, "%06d", vetor_chaves[0]);
					for (i = 1; i < ordem - 1; i++)
					{
						if(vetor_chaves[i] != -1) fprintf(ArvB, "%c%06d", CARACTERSEPARADOR, vetor_chaves[i]);
						else fprintf(ArvB, "%c      ", CARACTERSEPARADOR);
					}
					aux = getc(ArvB);
					fprintf(ArvB, "%08d", vetor_RRN[0]);
					for (i = 1; i < ordem - 1; i++)
					{
						if(vetor_RRN[i] != -1) fprintf(ArvB, "%c%08d", CARACTERSEPARADOR, vetor_RRN[i]);
						else fprintf(ArvB, "%c        ", CARACTERSEPARADOR);
					}
					aux = getc(ArvB);
					fprintf(ArvB, "%06d", vetor_filhos[0]);
					for (i = 1; i < ordem; i++)
					{
						if(vetor_filhos[i] != -1) fprintf(ArvB, "%c%06d", CARACTERSEPARADOR, vetor_filhos[i]);
						else fprintf(ArvB, "%c      ", CARACTERSEPARADOR);
					}

					/* atribui -1 a struct Promocao, sinalizando que o ajuste da Arvore acabou */
					Promocao.chave = -1;
				}
			}
		} while (Promocao.chave != -1);
}

int geraArquivoEstrutura(char *indice, int ordem, char *descricao)
{
	FILE *Indice, *Descricao;
	ApFila Fila, primeiroFila, ultimoFila;
	int *vetor_chaves, *vetor_filhos, i, j, pagina_atual, tam_bytes_pagina, nivel_atual = 0;
	char aux[9], aux2;

	Indice = fopen(indice, "r");

	/* se o arquivo com a Arvore B nao foi gerado ainda */
	if(!arqExistente(Indice)) return 0;

	Descricao = fopen(descricao, "w");

	/* obtencao da pagina do noh raiz, atraves do header da Arvore*/
	fseek(Indice, 19, SEEK_SET);
	fscanf(Indice, "%d", &pagina_atual);

	fprintf(Descricao, "Raiz: %d\n", pagina_atual);

	tam_bytes_pagina = calculaTamanhoPorPagina(ordem);

	/* Implementa uma fila como estrutura de dados para percorrer a Arvore B em largura,
	 * enfileirando os apontadores para os nos filhos de cada noh percorrido */
	Fila = (ApFila)Malloc(sizeof(fila));
	Fila->pagina = pagina_atual; //primeiro da fila eh a raiz
	Fila->pagina_eh_raiz = true;
	Fila->nivel = 1;
	Fila->prox = NULL;
	primeiroFila = Fila; //primeiroFila aponta para o noh analisado no momento
	ultimoFila = Fila; //ultimoFila atualiza a Fila, enfileirando os filhos

	/* aloca vetores */
	vetor_chaves = (int *)Malloc((ordem-1)*sizeof(int));
	vetor_filhos = (int *)Malloc((ordem)*sizeof(int));

	while (primeiroFila != NULL) //enquanto a fila nao acaba
	{
		/* seek para o noh a ser descrito */
		fseek(Indice, TAM_HEADER_ARVORE + ((primeiroFila->pagina)-1)*tam_bytes_pagina + 23, SEEK_SET);
		fscanf(Indice, "%d", &(*primeiroFila).num_chaves);
		for(i = 0; i < 14; i++) aux2 = getc(Indice);

		/* transferencia dos vetores de chaves e apontadores para filhos do disco
		 * para a memoria */
		for (i = 0; i < ordem - 1; i++)
		{
			for (j = 0; j < 6; j++) aux[j] = getc(Indice);
			aux[j] = '\0';
			vetor_chaves[i] = converteInt2(aux);
			aux2 = getc(Indice);
		}
		for (i = 0; i < (ordem-1)*8 + ordem-2 + 1; i++) aux2 = getc(Indice); //pula vetor de RRNs
		for (i = 0; i < ordem; i++)
		{
			for (j = 0; j < 6; j++) aux[j] = getc(Indice);
			aux[j] = '\0';
			vetor_filhos[i] = converteInt2(aux);
			if (vetor_filhos[i] != -1)
			{
				/* enfileira os apontadores para os nos filhos para futura descricao */
				ultimoFila->prox = (ApFila)Malloc(sizeof(fila));
				ultimoFila = ultimoFila->prox;
				ultimoFila->pagina = vetor_filhos[i];
				ultimoFila->pagina_eh_raiz = false;
				ultimoFila->nivel = primeiroFila->nivel + 1;
				ultimoFila->prox = NULL;
			}
			aux2 = getc(Indice);
		}
		/* fim da transferencia */

		/* se mudou de nivel na Arvore */
		if (primeiroFila->nivel > nivel_atual)
		{
			nivel_atual++;
			fprintf(Descricao, "Nivel %d da Arvore: \n", nivel_atual);
		}

		/* Faz a descricao da Arvore B, conforme formato especificado pelo enunciado */
		fprintf(Descricao, "\tNo %d : Total chaves=%d;\t", primeiroFila->pagina, primeiroFila->num_chaves);
		for (i = 0; i < primeiroFila->num_chaves; i++)
			fprintf(Descricao, "(%d,%06d),", vetor_filhos[i], vetor_chaves[i]);
		fprintf(Descricao, "(%d,)\n", vetor_filhos[i]);

		/* a fila anda... */
		primeiroFila = primeiroFila->prox;
	}

	/* Libera memoria usada pelos vetores e pela Fila */
	free(vetor_chaves);
	free(vetor_filhos);
	LiberaPilhaouFila(Fila);

	/* Fecha arquivos utilizados pela funcao */
	fclose(Indice);
	fclose(Descricao);
	return 1;
}

int pesquisaBaseDados(char **mensagens, char *dados, char *indice, int ordem)
{
	int chave, i, j, *vetor_chaves, *vetor_RRN, *vetor_filhos, pagina_atual, eh_folha, tam_bytes_pagina, maior = false;
	FILE *Dados, *Indice;
	char aux[9], aux2;
	Registro reg;

	Indice = fopen(indice, "r");

	/* se Arvore ainda nao foi gerada */
	if(!arqExistente(Indice)) return 0;

	printf("\n\n%s", mensagens[15]);
	scanf("%d", &chave); //chave a ser pesquisada na arvore

	Dados = fopen(dados, "r");
	tam_bytes_pagina = calculaTamanhoPorPagina(ordem);

	/* obtem pagina raiz atraves do header da Arvore */
	fseek(Indice, 19, SEEK_SET);
	fscanf(Indice, "%d", &pagina_atual);

	/* aloca vetores */
	vetor_chaves = (int*)Malloc((ordem-1)*sizeof(int));
	vetor_RRN = (int*)Malloc((ordem-1)*sizeof(int));
	vetor_filhos = (int*)Malloc((ordem)*sizeof(int));

	while (1)
	{
		fseek(Indice, TAM_HEADER_ARVORE + (pagina_atual-1)*tam_bytes_pagina + 33, SEEK_SET);
		aux2 = getc(Indice);
		if(aux2 == '1') eh_folha = true;
		else eh_folha = false;
		aux2 = getc(Indice); aux2 = getc(Indice); aux2 = getc(Indice); aux2 = getc(Indice);

		/* carrega vetores do disco para a memoria */
		for (i = 0; i < ordem - 1; i++)
		{
			for (j = 0; j < 6; j++) aux[j] = getc(Indice);
			aux[j] = '\0';
			vetor_chaves[i] = converteInt2(aux);
			aux2 = getc(Indice);
		}
		for (i = 0; i < ordem - 1; i++)
		{
			for (j = 0; j < 8; j++) aux[j] = getc(Indice);
			aux[j] = '\0';
			vetor_RRN[i] = converteInt2(aux);
			aux2 = getc(Indice);
		}
		for (i = 0; i < ordem; i++)
		{
			for (j = 0; j < 6; j++) aux[j] = getc(Indice);
			aux[j] = '\0';
			vetor_filhos[i] = converteInt2(aux);
			aux2 = getc(Indice);
		}

		/* procura no vetor na memoria, a chave a ser pesquisada */
		i = 0;
		while ((vetor_chaves[i] < chave) && (vetor_chaves[i] != -1))
		{
			if (i == ordem-2)
			{
				maior = true; //a chave possivelmente esta a direita da maior chave deste vetor
				break;
			}
			i++;
		}
		if (chave == vetor_chaves[i]) //achou a chave no noh
		{
			/* seek no arquivo de dados para o registro correspondente a chave pesquisada */
			fseek(Dados, vetor_RRN[i], SEEK_SET);

			/* copia das informacoes do registro do arquivo de dados para a struct Registro */
			for (i = 0; i < 6; i++) reg.RA[i] = getc(Dados); reg.RA[i] = '\0'; aux2 = getc(Dados);
			for (i = 0; i < 23; i++) reg.NOME[i] = getc(Dados); reg.NOME[i] = '\0'; aux2 = getc(Dados);
			for (i = 0; i < 14; i++) reg.CIDADE[i] = getc(Dados); reg.CIDADE[i] = '\0'; aux2 = getc(Dados);
			for (i = 0; i < 8; i++) reg.TEL[i] = getc(Dados); reg.TEL[i] = '\0'; aux2 = getc(Dados);
			for (i = 0; i < 8; i++) reg.ALT[i] = getc(Dados); reg.ALT[i] = '\0'; aux2 = getc(Dados);
			for (i = 0; i < 1; i++) reg.SEX[i] = getc(Dados); reg.SEX[i] = '\0'; aux2 = getc(Dados);
			for (i = 0; i < 2; i++) reg.CURSO[i] = getc(Dados); reg.CURSO[i] = '\0';

			/* imprime na tela as informacoes do registro encontrado para o usuario */
			printf("\n\n%s%s\n", mensagens[16], reg.RA);
			printf("%s%s\n", mensagens[17], reg.NOME);
			printf("%s%s\n", mensagens[18], reg.CIDADE);
			printf("%s%s\n", mensagens[19], reg.TEL);
			printf("%s%s\n", mensagens[20], reg.ALT);
			printf("%s%s\n", mensagens[21], reg.SEX);
			printf("%s%s\n", mensagens[22], reg.CURSO);

			/* fecha arquivos e libera memoria */
			fclose(Dados);
			fclose(Indice);
			free(vetor_chaves);
			free(vetor_RRN);
			free(vetor_filhos);
			return 1;
		}
		else //caso nao encontrou a chave na pagina atual
		{
			if (eh_folha) //se pagina atual era folha, a chave nao existe na Arvore
			{
				printf("\n\n%s\n", mensagens[23]);

				/* fecha arquivos e libera memoria */
				fclose(Dados);
				fclose(Indice);
				free(vetor_chaves);
				free(vetor_RRN);
				free(vetor_filhos);
				return 1;
			}
			else //desce na Arvore B
			{
				if (!maior) pagina_atual = vetor_filhos[i];
				else pagina_atual = vetor_filhos[i+1];
				maior = false;
			}
		}
	}

	return 1;
}

int main(int argc, char *argv[])
{
	int ordem;
	char *mensagens[NUMEROMENSAGENS];
	char *Ordem = argv[1], *dados = argv[2], *indice = argv[3], *desprezadas = argv[4], *descricao = argv[5];

	/*carrega arquivo de configuracao*/
	carregaConfiguracoes(&mensagens[0]);

	/*verifica se o numero de argumentos esta correto*/
	if (argc < 6)
	{
		printf("%s\n\n", mensagens[0]);
	    exit(EXIT_FAILURE);
	}

	ordem = converteInt2(Ordem);

	if (!verificaParametros(mensagens, ordem, dados)) exit(EXIT_FAILURE);

	/*cardapio com as opcoes disponiveis para o usuario*/
	cardapio(mensagens, ordem, dados, indice, desprezadas, descricao);

	return 0;
}
